package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0064 
* @author      : ganwei 
* @date        : 2020年5月18日 
* @Description : TODO 
*/
public class Leetcode0064 {
    public int minPathSum(int[][] grid) {
    	if(grid.length == 0) {
    		return 0;
    	}
    	int m = grid.length;
    	int n = grid[0].length;
    	int[][] dp = new int[m][n];
    	//base case
    	int rowsum = 0;
    	for(int i = 0; i < m; i++) {	
    		rowsum += grid[i][0];
    		dp[i][0] = rowsum;
    		
    	}
    	int colsum = 0;
    	for(int i = 0; i < n; i++) {
    		colsum += grid[0][i];
    		dp[0][i] = colsum;
    	}
    	for(int i = 1; i < m; i++) {
    		for(int j = 1; j < n; j++) {
    			dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
    		}
    	}
    	
    	return dp[m-1][n-1];
    }
    

    
    public static void main(String[] args) {
    	Leetcode0064 l0064 = new Leetcode0064();
    	int[][] grid = {  {1,3,1},
    			  {1,5,1},
    			  {4,2,1}};
    	
    	System.out.println(l0064.minPathSum(grid));
    }
}

